package com.fw.leetcode.greedy;

import com.fw.leetcode.LeetCode;

import java.util.Arrays;

/**
 * 455. Assign Cookies
 *
 * Assume you are an awesome parent and want to give your children some cookies.
 * But, you should give each child at most one cookie.
 *
 * Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with;
 * and each cookie j has a size s[j].
 * If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content.
 * Your goal is to maximize the number of your content children and output the maximum number.
 *
 * Example 1:
 *  Input: g = [1,2,3], s = [1,1]
 *  Output: 1
 *  Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
 *               And even though you have 2 cookies, since their size is both 1, you could only
 *               make the child whose greed factor is 1 content.
 *               You need to output 1.
 *
 * Example 2:
 *  Input: g = [1,2], s = [1,2,3]
 *  Output: 2
 *  Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
 *               You have 3 cookies and their sizes are big enough to gratify all of the children,
 *               You need to output 2.
 *
 * Constraints:
 *  1 <= g.length <= 3 * 10^4
 *  0 <= s.length <= 3 * 10^4
 *  1 <= g[i], s[j] <= 2^31 - 1
 */
public class Num_0455 implements LeetCode {

    private interface Solution {
        int findContentChildren(int[] g, int[] s);

        default void assertExpected(int[] g, int[] s, int expected) {
            if (findContentChildren(g, s) != expected) {
                findContentChildren(g, s);
            }
        }
    }

    private static class MySolution implements Solution {

        @Override
        public int findContentChildren(int[] g, int[] s) { // 分饼干 贪心+排序+双指针：时O(nlog n + mlog m) 空O(logm+logn)
            /*
             * 饼干竟然不能掰开分，也不能组合分
             */
            Arrays.sort(g); // 时O(nlog n + mlog m) 空O(logm+logn)
            Arrays.sort(s);
            int i = 0;
            int j = 0;
            int count = 0; // 统计被分得人数
            while (i < g.length && j < s.length) { // 时O(m+n) 空O(1)
                if (g[i] <= s[j]) {
                    count++; // 满足孩子欲望大小饼干
                    i++;
                }
                j++;
            }
            return count;
        }
    }

    public static void main(String[] args) {
        Solution solution = new MySolution();
        solution.assertExpected(new int[]{1,2,3}, new int[]{1,1}, 1);
        solution.assertExpected(new int[]{1,2}, new int[]{1,2,3}, 2);
    }
}
